栈和队列——设计一个有getMin()的栈

Posted on | In ,

题目：实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回最小元素的操作。
要求：可以使用现有的栈结构。

实现：设计两个栈，一个栈dataStack保存输入的数据；另一个栈minStack保存每一步的最小值。
方法一：
1.压入规则push()
当前数据为newNum，压入dataStack。然后判断minStack是否为空：
1）如果为空，则将newNum压入minStack；
2）如果不为空，比较栈顶元素与newNum的大小：
（1）如果newNum更小或相等，则将newNum压入minStack；
（2）如果minStack栈顶元素更小，不做任何处理。
2.弹出数据规则pop()
先弹出dataStack栈顶数据，记为value。
1）当value等于minStack栈顶元素时，弹出minStack栈顶元素；
2）当value大于minStack栈顶元素时，stackMin不弹出栈顶元素；
3）返回value。
3.查找当前栈中的最小值getMin()
minStack栈顶元素记为最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.util.Stack;
public class MyStack {
	private Stack<Integer> dataStack;
	private Stack<Integer> minStack;
	public MyStack(){
		dataStack = new Stack<Integer>();
		minStack = new Stack<Integer>();
	}
	//压入规则
	public void push(int newNum) {
		dataStack.push(newNum);
		if (minStack.isEmpty()) {
			minStack.push(newNum);
		} else if (newNum <= minStack.peek()) {
			minStack.push(newNum);
		}	
//		} else {
//			if (newNum <= minStack.peek()) {
//				minStack.push(newNum);
//			} else{ //newNum > minStack.peek()这种情况不作任何操作，则不用写出来
//				return;
//			}
//		}
	}	
	//弹出规则
	public int pop(){
		if (dataStack.isEmpty()) {
			throw new RuntimeException("Your stack is empty!");
			//抛异常给上级调用
		}
		int val = dataStack.pop();
		if (val == dataStack.peek()) {
			minStack.pop();
		} //其它情况不做任何处理，则不用写。
		return val;
		/*while(!dataStack.isEmpty()) {
			int val = dataStack.pop();
			if(val == minStack.peek()) {
				minStack.pop();
			} 
			return val;
		}用这种方法无法返回val，val必须在pop()的第一层方法里*/	
	}
	//返回栈内最小元素
	public int getMin(){
		if (minStack.isEmpty()) {
			throw new RuntimeException("Your stack is empty!");
		}
		return minStack.peek();
	}
1
2
3
4
5
6
7
8
9
10
	//Test
	public static void main(String[] args) {
		MyStack stack = new MyStack();
		stack.push(4);
		stack.push(1);
		stack.push(3);
		stack.push(5);
		System.out.println(stack.getMin());
	}
}

方法二：

  1. 压栈规则push()
    当前数据为newNum，压入dataStack。然后判断minStack是否为空：
    1）如果为空，则将newNum压入minStack；
    2）如果不为空，比较栈顶元素与newNum的大小：
    （1）如果newNum更小或相等，则将newNum压入minStack；
    （2）如果minStack栈顶元素更小，则将栈顶元素重复入栈。
    1
    2
    3
    4
    5
    6
    7
    8
    dataStack.push(newNum);
    if (minStack.isEmpty()) {
    	minStack.push(newNum);
    } else if (newNum <= minStack.peek()) {
    	minStack.push(newNum);
    } else{
    	minStack.push(minStack.peek());
    }
  2. 弹出数据规则pop()
    先弹出dataStack栈顶数据，记为value。弹出minStack栈顶数据
    1
    2
    3
    4
    5
    if (dataStack.isEmpty()) {
    	throw new RuntimeException("Your stack is empty!");
    }
    minStack.pop();
    return dataStack.pop();

对比方案一和方案二，所有操作的时间复杂度都是O(1)，空间复杂度都是O(n)。方案一入栈稍省空间，但弹出操作稍费时间；方案二入栈稍费空间，但弹出操作稍省时间